Examples

Example 1

Angle = 30°
Start = A
Rules:
  A > A[+A][-A]B
  B > [--B]A
Number of recursions = 7

Example 2

Angle = 60°
Start = A
Rules:
  A > -B+B+B+B+B+B
  B > B[--CCA][-CCA]B
  C > CC
Number of recursions = 7

Example 3

Angle = 45°
Start = A
Rules:
  A > [----AAB][--AAB][++AAB]AAB
  B > [-C][+C][--C][++C][---C][+++C]
  C > CAB
Number of recursions = 6

Example 4

Angle = 72°
Start = A
Rules:
  A > [-AAB][--AAB][+AAB][++AAB]AAB
  B > [-C][+C][--C][++C]CA
  C > CC
Number of recursions = 5

Example 5

Angle = 60°
Start = a
Rules:
  a > -B+B+B+B+B+B
  B > BB[-CCa]
  C > CC
Number of recursions = 9

Example 6

Angle = 72°
Start = A
Rules:
  A > B+B+B+B+B
  B > [-CCA]BB
  C > CC
Number of recursions = 9

Example 7

Angle = 45°
Start = A
Rules:
  A > +A-B-B[B]
  B > -B+A+A[A]
Number of recursions = 8

Example 8

Angle = 90°
Start = A
Rules:
  A > AA[-A][+A]
Number of recursions = 8

Example 9

Angle = 30°
Start = A
Rules:
  A > AcbcA
  b > [+A][-A][++A][--A][+++A][---A][++++A][----A][+++++A][-----A]
  c > bAb
Number of recursions = 6

Example 10

Angle = 30°
Start = AB
Rules:
  A > B--B
  B > AA+++AA
Number of recursions = 12

Example 11

Angle = 30°
Start = x
Rules:
  x > FFF[+FFF+FFF+FF+FF+F+Fx][-FFF-FFF-FF-FF-F-Fx]Fx
  F > FFx
Number of recursions = 6

Example 12

Angle = 45°
Start = A
Rules:
  A > AB
  B > A[++C][--C]
  C > C[+C][-C]A
Number of recursions = 10

Example 13

Angle = 25°
Start = -x
Rules:
  x > F+[[x]-x]-F[-Fx]+x
  F > FF
Number of recursions = 7

Example 14

Angle = 90°
Start = b
Rules:
  A > AA
  b > AbA+AbA+AbA
Number of recursions = 9

Example 15

Angle = 115°
Start = A
Rules:
  A > A+A-A
Number of recursions = 11

Example 16

Angle = 90°
Start = A
Rules:
  A > A[+AA][-AA]B
  B > ABA
Number of recursions = 7

Example 17

Angle = 6°
Start = x
Rules:
  x > FFF[+FF+FF+FF+F+Fx][-FF-FF-FF-F-Fx]FFFFFFFFFFFFFFx
  F > FF
Number of recursions = 8

What is a Lindenmayer System?

• Begin with a string of characters (a “word”).
  • For example, let’s start with “A”.
• Define replacement rules.

  • Example:

    • Replace “A” with “BO”
    • Replace “B” with “BA”
    • Replace “O” with “BA”

  • First few recursions:

    0. “A”
    1. “BO”
    2. “BABA”
    3. “BABOBABO”
    4. “BABOBABABABOBABA”
    5. “BABOBABABABOBABOBABOBABABABOBABO”

Recursive Replacement of Letters

• Start:

  • A

• Rules:

  • A \(\to\) ART-
  • R \(\to\) RAT-
  • T \(\to\) TAR-
  • - \(\to\) -

• Notice, “-” is constant. We usually don’t include constants in the rules. If a character does not have a replacement rule, we assume it is a constant.

• Find the recursions (the iterations):

  0. A
  1. ART-
  2. ART-RAT-TAR-
  3. ART-RAT-TAR--RAT-ART-TAR--TAR-ART-RAT--
  4. ART-RAT-TAR--RAT-ART-TAR--TAR-ART-RAT---RAT-ART-TAR--ART-RAT-TAR--TAR-ART-RAT---TAR-ART-RAT--ART-RAT-TAR--RAT-ART-TAR---

Recursive Replacement of Letters

• Start:

  • “x”

• Rules:

  • “A” \(\to\) “A-”
  • “x” \(\to\) “Ax”
  • “-” \(\to\) “-” (Notice that since “-” is replaced with “-”, it is a constant. We usually do not list constants in the rules; constants are implied by not having a rule.)

• Find the recursions (the iterations):

  0. “x”
  1. “Ax”
  2. “A-Ax”
  3. “A–A-Ax”
  4. “A—A–A-Ax”

Okay, but what about those pictures?

• Turtle Graphics! A turtle drags a pen and follows commands.
  • “F” = Forward one step
  • “+” = Turn right by 90°
  • “-” = Turn left by 90°
  • “[” = Record current position, top of a list
  • “]” = Teleport to top-of-list position, and remove position from list

You try!

• “F” = Forward one step
• “+” = Turn right by 90°
• “-” = Turn left by 90°
• “[” = Record current position, top of a list
• “]” = Teleport to top-of-list position, and remove position from list

Draw the following string:

\[\mathtt{FFF[+FFF+FFF+FF+FF+F+F][-FFF-FFF-FF-FF-F-F]F}\]

Correct answer

Scratch

Over a few days we will code the following programs in Scratch:

• Use keyboard buttons to control turtle using the following moves:
  • Move forward
  • Turn right
  • Turn left
  • Hop forward (and do not draw)
  • Save position at top of list
  • Return to top-of-list position and delete position from list
• Copy and paste a string of characters (a “word”) into Scratch, each character corresponding to a move; turtle draws whole picture.
  • We can use a L-system string generator to create the strings.